"""
贪心策略（Greedy Strategy）详解：

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，
从而希望导致结果是全局最好或最优的算法。

贪心策略的特点：
1. 局部最优选择：每一步都选择当前最优的解
2. 不可回溯：一旦做出选择，就不再改变
3. 高效性：通常时间复杂度较低
4. 不保证全局最优：在某些问题上可能无法得到最优解

贪心算法的适用条件：
1. 贪心选择性质：局部最优解能导致全局最优解
2. 最优子结构：问题的最优解包含其子问题的最优解

常见应用场景：
- 找零钱问题（硬币面额满足特定条件时）
- 最小生成树（Prim、Kruskal算法）
- 最短路径（Dijkstra算法）
- 霍夫曼编码
- 活动选择问题
"""


def greedy_algorithm_example():
    """
    贪心策略示例：活动选择问题
    目标：选择最多的互不重叠的活动
    """
    # 活动格式：(开始时间, 结束时间)
    activities = [
        (1, 4), (3, 5), (0, 6), (5, 7),
        (3, 9), (5, 9), (6, 10), (8, 11),
        (8, 12), (2, 14), (12, 16)
    ]

    # 按结束时间排序（贪心策略：总是选择结束最早的活动）
    activities.sort(key=lambda x: x[1])

    selected = []
    last_end_time = -1

    for start, end in activities:
        if start >= last_end_time:  # 活动不重叠
            selected.append((start, end))
            last_end_time = end

    return selected


print("=== 贪心策略示例：活动选择问题 ===")
selected_activities = greedy_algorithm_example()
print("选择的活动（开始时间, 结束时间）:")
for i, activity in enumerate(selected_activities, 1):
    print(f"活动{i}: {activity}")
print(f"总共选择了 {len(selected_activities)} 个活动")
print()